class Solution {
public:
    vector<int> topSort(vector<vector<int> >& edges,vector<int>& indeg){
        vector<int> ret;
        queue<int> que;
        for(int i = 0;i < indeg.size();i++){
            if(indeg[i] == 0){
                que.push(i);
            }
        }
        while(!que.empty()){
            int u = que.front();
            que.pop();
            ret.push_back(u);
            for(int& v : edges[u]){
                indeg[v]--;
                if(indeg[v] == 0){
                    que.push(v);
                }
            }
        }
        return ret.size() == edges.size() ? ret : vector<int>();
    }
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for(int i = 0;i < n;i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }
        
        vector<vector<int> > edgesItem(n),edgesGroup(m);
        vector<int> indegItem(n),indegGroup(m);
        for(int i = 0;i < n;i++){
            for(int& j : beforeItems[i]){
                edgesItem[j].push_back(i);
                indegItem[i]++;
                
                if(group[j] != group[i]){
                    edgesGroup[group[j]].push_back(group[i]);
                    indegGroup[group[i]]++;
                }
            }
        }
        
        vector<int> ret;
        vector<int> topGroup = topSort(edgesGroup,indegGroup);
        if(topGroup.size() == 0){
            return ret;
        }
        vector<int> topItem = topSort(edgesItem,indegItem);
        if(topItem.size() == 0){
            return ret;
        }
        
        unordered_map<int,vector<int> > ump;
        for(int& i : topItem){
            ump[group[i]].push_back(i);
        }
        
        for(int& j : topGroup){
            vector<int> Item = ump[j];
            for(int& k : Item){
                ret.push_back(k);
            }
        }
        return ret;
    }
};
